package com.mlh.sort;

public class HeapSort {
    public static void main(String[] args) {
        int[]arr={53,17,78,9,45,65,87,32,345,7,67,1,1,1,1,1,1,1,45,6,7,8,5,3,-3};
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);
        for (int temp:arr){
            System.out.println(temp);
        }
    }
    //堆排序
    //看完ONENOTE上的解法过程再来看代码  遵循上面的思想
    //树用数组形式表现
    //该方法是将某一结点下坠的过程
    public void heapAdjust(int[]arr,int head,int arrLength){//传入头节点对应的数组下标和数组本身
        while(2*(head+1)-1<arrLength){//看head节点是否有左子树  没有说明是叶子节点 直接退出循环
            if(2*(head+1)>=arrLength){
                //没有右子树
                if(arr[head]>=arr[2*(head+1)-1]){
                    break;
                }else{
                    //都没有右子树了，说明已经是最后一层了
                    //此时交换一下值即可
                    int temp=arr[head];
                    arr[head]=arr[2*(head+1)-1];
                    arr[2*(head+1)-1]=temp;
                    break;
                }
            }
            //左右子树都有
            //选出左右子树大的出来和head比较
            //如果左子树大
            if(arr[2*(head+1)-1]>arr[2*(head+1)]){
                //如果都左右子树都小于head 则break完成大根堆的建立
                if(arr[head]>=arr[2*(head+1)-1]){
                    break;
                }else{
                    //如果左子树大于head
                    //两者交换位置，head等于左子树位置继续循环
                    int temp=arr[head];
                    arr[head]=arr[2*(head+1)-1];
                    arr[2*(head+1)-1]=temp;
                    head=2*(head+1)-1;
                }
            }else{//如果右子树大
                //右子树又小于head  直接退出
                if(arr[head]>=arr[2*(head+1)]){
                    break;
                }else{
                    //如果右子树大于head
                    //两者交换位置，head等于右子树位置继续循环
                    int temp=arr[head];
                    arr[head]=arr[2*(head+1)];
                    arr[2*(head+1)]=temp;
                    head=2*(head+1);
                }
            }
        }
    }

    //接下来就可以写堆排序了
    public int[] heapSort(int[]arr){
        int arrLength= arr.length;
        //先构建大根堆
        //调整为大根堆的方法就是从分支节点开始 调用heapAdjust方法 直到根节点结束
        for(int i=arr.length/2-1;i>=0;i--){
            heapAdjust(arr,i,arrLength);
        }
        //将头节点（此时为最大值）和数组尾调换位置  在进行下坠调整为大根堆 以此循环 最终得到有序数组
        for(int i=0;i< arr.length-1;i++){
            int temp=arr[0];
            arr[0]=arr[arrLength-1];//因为arrLength不是数组下标 所以要-1
            arr[arrLength-1]=temp;
            //根节点下坠
            arrLength--;//因为原本的根节点调换到数组尾  就确定位置了  下坠的时候不要涉及到以确定好为位置的元素
            heapAdjust(arr,0,arrLength);
        }
        return arr;
    }

}
